#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int i = 0;
        int n = pushed.size();
        for (auto& e : popped)
        {
            while ((st.empty() || st.top() != e) && i < n)
            {
                st.push(pushed[i++]);
            }
            if (st.empty() || st.top() != e)
                return false;

            st.pop();
        }

        return true;
    }
};